Proceedings of the Third International Conference on Web Search and Web Data Mining

Choosing your own adventure automatic taxonomy generation to permit many paths.

Mining Anchor Text Trends for Retrieval.
Abstract. Anchor text has been considered as a useful resource to complement the representation of target pages and is broadly used in web search. However, previous research only uses anchor text of a single snapshot to improve web search. Historical trends of anchor text importance have not been well modeled in anchor text weighting strategies. In this paper, we propose a novel temporal anchor text weighting method to incorporate the trends of anchor text creation over time, which combines historical weights of anchor text by propagating the anchor text weights among snapshots over the time axis. We evaluate our method on a real-world web crawl from the Stanford WebBase. Our results demonstrate that the proposed method can produce a significant improvement in ranking quality. 1
Mining Neighbors%27 Topicality to Better Control Authority Flow.
Abstract. Web pages are often recognized by others through contexts. These contexts determine how linked pages influence and interact with each other. When differentiating such interactions, the authority of web pages can be better estimated by controlling the authority flows among pages. In this work, we determine the authority distribution by examining the topicality relationship between associated pages. In addition, we find it is not enough to quantify the influence of authority propagation from only one type of neighbor, such as parent pages in PageRank algorithm, since web pages, like people, are influenced by diverse types of neighbors within the same network. We propose a probabilistic method to model authority flows from different sources of neighbor pages. In this way, we distinguish page authority interaction by incorporating the topical context and the relationship between associated pages. Experiments on the 2003 and 2004 TREC Web Tracks demonstrate that this approach outperforms other competitive topical ranking models and produces a more than 10 % improvement over PageRank on the quality of top 10 search results. When increasing the types of incorporated neighbor sources, the performance shows stable improvements. 1
A probabilistic model for personalized tag prediction.
Social tagging systems have become increasingly popular for sharing and organizing web resources. Tag recommendation is a common feature of social tagging systems. Social tagging by nature is an incremental process, meaning that once a user has saved a web page with tags, the tagging system can provide more accurate predictions for the user, based on the user’s incremental behavior. However, existing tag prediction methods do not consider this important factor, in which their training and test datasets are either split by a fixed time stamp or randomly sampled from a larger corpus. In our temporal experiments, we perform a time-sensitive sampling on an existing public dataset, resulting in a new scenario which is much closer to “real-world”. In this paper, we address the problem of tag prediction by proposing a probabilistic model for personalized tag prediction. The model is a Bayesian approach, and integrates three factors— an ego-centric effect, environmental effects and web page content. Two methods—both intuitive calculation and learning optimization—are provided for parameter estimation. Pure graphbased methods which may have significant constraints (such as every user, every item and every tag has to occur in at least p posts) cannot make a prediction in most “real world ” cases while our model improves the F-measure by over 30 % compared to a leading algorithm on a publicly-available real-world dataset.
Freshness matters in flowers%2C food%2C and web authority.
The collective contributions of billions of users across the globe each day result in an ever-changing web. In verticals like news and real-time search, recency is an obvious significant factor for ranking. However, traditional link-based web ranking algorithms typically run on a single web snapshot without concern for user activities associated with the dynamics of web pages and links. Therefore, a stale page popular many years ago may still achieve a high authority score due to its accumulated in-links. To remedy this situation, we propose a temporal web link-based ranking scheme, which incorporates features from historical author activities. We quantify web page freshness over time from page and in-link activity, and design a web surfer model that incorporates web freshness, based on a temporal web graph composed of multiple web snapshots at different time points. It includes authority propagation among snapshots, enabling link structures at distinct time points to influence each other when estimating web page authority. Experiments on a real-world archival web corpus show our approach improves upon PageRank in both relevance and freshness of the search results.
Looking into the past to better classify web spam.
Web spamming techniques aim to achieve undeserved rankings in search results. Research has been widely conducted on identifying such spam and neutralizing its influence. However, existing spam detection work only considers current information. We argue that historical web page information may also be important in spam classification. In this paper, we use content features from historical versions of web pages to improve spam classification. We use supervised learning techniques to combine classifiers based on current page content with classifiers based on temporal features. Experiments on the WEBSPAM-UK2007 dataset show that our approach improves spam classification F-measure performance by 30% compared to a baseline classifier which only considers current page content.
Capturing page freshness for web search.
Freshness has been increasingly realized by commercial search engines as an important criteria for measuring the quality of search results. However, most information retrieval methods focus on the relevance of page content to given queries without considering the recency issue. In this work, we mine page freshness from web user maintenance activities and incorporate this feature into web search. We first quantify how fresh the web is over time from two distinct perspectives—the page itself and its in-linked pages—and then exploit a temporal correlation between two types of freshness measures to quantify the confidence of page freshness. Results demonstrate page freshness can be better quantified when combining with temporal freshness correlation. Experiments on a realworld archival web corpus show that incorporating the combined page freshness into the searching process can improve ranking performance significantly on both relevance and freshness.
Looking into the past to better classify web spam.
Web spamming techniques aim to achieve undeserved rankings in search results. Research has been widely conducted on identifying such spam and neutralizing its influence. However, existing spam detection work only considers current information. We argue that historical web page information may also be important in spam classification. In this paper, we use content features from historical versions of web pages to improve spam classification. We use supervised learning techniques to combine classifiers based on current page content with classifiers based on temporal features. Experiments on the WEBSPAM-UK2007 dataset show that our approach improves spam classification F-measure performance by 30% compared to a baseline classifier which only considers current page content.
Vetting the links of the web.
Many web links mislead human surfers and automated crawlers because they point to changed content, out-of-date information, or invalid URLs. It is a particular problem for large, well-known directories such as the dmoz Open Directory Project, which maintains links to representative and authoritative external web pages within their various topics. Therefore, such sites involve many editors to manually revisit and revise links that have become out-of-date. To remedy this situation, we propose the novel web mining task of identifying outdated links on the web. We build a general classification model, primarily using local and global temporal features extracted from historical content, topic, link and time-focused changes over time. We evaluate our system via five-fold cross-validation on more than fifteen thousand ODP external links selected from thirteen top-level categories. Our system can predict the actions of ODP editors more than 75 % of the time. Our models and predictions could be useful for various applications that depend on analysis of web links, including ranking and crawling.
Vetting the links of the web.
Many web links mislead human surfers and automated crawlers because they point to changed content, out-of-date information, or invalid URLs. It is a particular problem for large, well-known directories such as the dmoz Open Directory Project, which maintains links to representative and authoritative external web pages within their various topics. Therefore, such sites involve many editors to manually revisit and revise links that have become out-of-date. To remedy this situation, we propose the novel web mining task of identifying outdated links on the web. We build a general classification model, primarily using local and global temporal features extracted from historical content, topic, link and time-focused changes over time. We evaluate our system via five-fold cross-validation on more than fifteen thousand ODP external links selected from thirteen top-level categories. Our system can predict the actions of ODP editors more than 75 % of the time. Our models and predictions could be useful for various applications that depend on analysis of web links, including ranking and crawling.
Incorporating Participant Reputation in Community%2DDriven Question Answering Systems.
Community-driven Question Answering services are gaining increasing attention with tens of millions of users and hundreds of millions of posts in recent years. Due to its size, there is a need for users to be able to search these large question answer archives and retrieve high quality content. Research work shows that user reputation modeling makes a contribution when incorporated with relevance models. However, the effectiveness of different link analysis approaches and how to embed topical information—as a user may have different expertise in various areas—are still open questions. In this work, we address these two research questions by first reviewing different link analysis schemes—especially discussing the use of PageRank-based methods since they are less commonly utilized in user reputation modeling. We also introduce Topical Page-Rank analysis for modeling user reputation on different topics. Comparative experimental results on data from Yahoo! Answers show that PageRank-based approaches are more effective than HITS-like schemes and other heuristics, and that topical link analysis can improve performance.
Incorporating Participant Reputation in Community%2DDriven Question Answering Systems.
Community-driven Question Answering services are gaining increasing attention with tens of millions of users and hundreds of millions of posts in recent years. Due to its size, there is a need for users to be able to search these large question answer archives and retrieve high quality content. Research work shows that user reputation modeling makes a contribution when incorporated with relevance models. However, the effectiveness of different link analysis approaches and how to embed topical information—as a user may have different expertise in various areas—are still open questions. In this work, we address these two research questions by first reviewing different link analysis schemes—especially discussing the use of PageRank-based methods since they are less commonly utilized in user reputation modeling. We also introduce Topical Page-Rank analysis for modeling user reputation on different topics. Comparative experimental results on data from Yahoo! Answers show that PageRank-based approaches are more effective than HITS-like schemes and other heuristics, and that topical link analysis can improve performance.
A classification%2Dbased approach to question answering in discussion boards.
Discussion boards and online forums are important platforms for people to share information. Users post questions or problems onto discussion boards and rely on others to provide possible solutions and such question-related content sometimes even dominates the whole discussion board. However, to retrieve this kind of information automatically and effectively is still a non-trivial task. In addition, the existence of other types of information (e.g., announcements, plans, elaborations, etc.) makes it difficult to assume that every thread in a discussion board is about a question. We consider the problems of identifying question-related threads and their potential answers as classification tasks. Experimental results across multiple datasets demonstrate that our method can significantly improve the performance in both question detection and answer finding subtasks. We also do a careful comparison of how different types of features contribute to the final result and show that non-content features play a key role in improving overall performance. Finally, we show that a ranking scheme based on our classification approach can yield much better performance than prior published methods.
Counting ancestors to estimate authority.
The AncestorRank algorithm calculates an authority score by using just one characteristic of the web graph—the number of ancestors per node. For scalability, we estimate the number of ancestors by using a probabilistic counting algorithm. We also consider the case in which ancestors which are closer to the node have more influence than those farther from the node. Thus we further apply a decay factor δ on the contributions from successively earlier ancestors. The resulting authority score is used in combination with a content-based ranking algorithm. Our experiments show that as long as δ is in the range of [0.1, 0.9], AncestorRank can greatly improve BM25 performance, and in our experiments is often better than PageRank.
Web page classification Features and algorithms.

Performance comparison of different multicast routing strategies in disruption tolerant networks.
Abstract—Disruption Tolerant Networks (DTNs) technologies are emerging solutions to networks that experience frequent partitions. As a result, multicast design for DTNs is a considerably more difficult problem compared to that of Internet and mobile ad hoc networks. In this paper, we first investigate three basic DTN multicast strategies, including unicast-based multicast (U-Multicast), static-tree-based multicast (ST-Multicast) and dynamic-tree-based multicast (DT-Multicast). Then we focus on studying two DT-Multicast methods: Dynamic Tree Based Routing (DTBR) and On-demand Situation-aware Multicast (OS-Multicast), which address the challenges of utilizing opportunistic connectivity to conduct one-to-many data communication in DTNs. Performances of different multicast approaches are evaluated by simulations. Our results show that DT-Multicast approaches can achieve higher message delivery ratio than the other strategies. Also, to get better performance, we recommend that system designers select OS-Multicast when the traffic load is low and select DTBR when the traffic load is high respectively. Keywords-disruption/delay tolerant networks; intermittently connected networks; dynamic multicasting; performance evaluation
Separate and inequal preserving heterogeneity in topical authority flows.
Web pages, like people, are often known by others in a variety of contexts. When those contexts are sufficiently distinct, a page’s importance may be better represented by multiple domains of authority, rather than by one that indiscriminately mixes reputations. In this work we determine domains of authority by examining the contexts in which a page is cited. However, we find that it is not enough to determine separate domains of authority; our model additionally determines the local flow of authority based upon the relative similarity of the source and target authority domains. In this way, we differentiate both incoming and outgoing hyperlinks by topicality and importance rather than treating them indiscriminately. We find that this approach compares favorably to other topical ranking methods on two real-world datasets and produces an approximately 10 % improvement in precision and quality of the top ten results over PageRank.
Classifiers without borders incorporating fielded text from neighboring web pages.
Information retrieval on mind maps – what could it be
Explorations in tag suggestion and query expansion.
The query used in a search system is only an approximation to the user’s true information need, and as a result, many factors can reduce the quality of search results. One is query ambiguity, causing searchers with different needs to issue the same query. For example, for the query java, some users may want to find java tutorial while others may want to download java software. Other factors include a vocabulary mismatch and a lack of knowledge regarding the contents of the document collection. In any case, many users benefit from assistance in forming a good query. As a result, some commercial services provide query suggestions for many queries. In this paper, we propose a Tag Suggestion System that takes advantage of tags associated with query results to expand a searcher’s query. Since not every web page is associated with existing tags, we first build an auto-tagging system which can assign multiple tags to web pages, including news, blogs, etc. The current system contains the most popular 140 tags in del.icio.us, with high precision performance. A small user study is performed to evaluate anecdotally the performance of our Tag Suggestion System, showing better quality than the query suggestion mechanisms provided by Yahoo! and Google. The result pages of expanded queries generated by the Tag Suggestion System are also significantly better than those of the Google original system.
Connecting P2P to the web Lessons from a prototype Gnutella%2DWWW gateway.

Adversarial Information Retrieval on the Web %28AIRWeb 2007%29.

Introduction to special section on adversarial issues in Web search.

From Whence Does Your Authority Come%3F Utilizing Community Relevance in Ranking.
A web page may be relevant to multiple topics; even when nominally on a single topic, the page may attract attention (and thus links) from multiple communities. Instead of indiscriminately summing the authority provided by all pages, we decompose a web page into separate subnodes with respect to each community pointing to it. Utilizing the relevance of such communities allows us to better model the semantic structure of the Web, leading to better estimates of authority for a given query. We apply a total of eighty queries over two real-world datasets to demonstrate that the use of community decomposition can consistently and significantly improve upon Page-Rank’s top-ten results.
Measuring Similarity to Detect Qualified Links.
The success of link-based ranking algorithms is achieved based on the assumption that links imply merit of the target pages. However, on the real web, there exist links for purposes other than to confer authority. Such links bring noise into link analysis and harm the quality of retrieval. In order to provide high quality search results, it is important to detect them and reduce their influence. In this paper, a method is proposed to detect such links by considering multiple similarity measures over the source pages and target pages. With the help of a classifier, these noisy links are detected and dropped. After that, link analysis algorithms are performed on the reduced link graph. The usefulness of a number of features are also tested. Experiments across 53 query-specific datasets show that the result of our approach is able to boost Bharat and Henzinger’s imp algorithm by around 9 % in terms of precision. It also outperforms a previous approach focusing on link spam detection. 1
SHIM a scalable hierarchical inter%2Ddomain multicast approach for disruption tolerant networks.
Abstract—Disruption Tolerant Network (DTN) technologies are emerging solutions to networks that experience frequent partitions. In this paper, we propose the scalable hierarchical inter-domain multicast (SHIM) approach for DTNs. SHIM has the following characteristics: i) it is capable of delivering multicast messages to receivers distributed in different domains; ii) the size of the membership information maintained by the source leader is determined by its out-degree in the leader layer, no matter how large the number of the real receivers is; and iii) it at least doubles the message delivery efficiency than that of directly extending the existing intra-domain DTN multicast methods to perform the inter-domain multicast operations. Our results also show that the message delivery ratio of SHIM can be improved to be almost 100 % when the custodian transfer functionality is enabled in the overall networks.
Winnowing wheat from the chaff propagating trust to sift spam from the web.

Ranking by community relevance.

A cautious surfer for PageRank.

Knowing a web page by the company it keeps.
Web page classification is important to many tasks in information retrieval and web mining. However, applying traditional textual classifiers on web data often produces unsatisfying results. Fortunately, hyperlink information provides important clues to the categorization of a web page. In this paper, an improved method is proposed to enhance web page classification by utilizing the class information from neighboring pages in the link graph. The categories represented by four kinds of neighbors (parents, children, siblings and spouses) are combined to help with the page in question. In experiments to study the effect of these factors on our algorithm, we find that the method proposed is able to boost the classification accuracy of common textual classifiers from around 70 % to more than 90 % on a large dataset of pages from the Open Directory Project, and outperforms existing algorithms. Unlike prior techniques, our approach utilizes same-host links and can improve classification accuracy even when neighboring pages are unlabeled. Finally, while all neighbor types can contribute, sibling pages are found to be the most important.
Propagating Trust and Distrust to Demote Web Spam.
Web spamming describes behavior that attempts to deceive search engine&#039;s ranking algorithms. TrustRank is a recent algorithm that can combat web spam by propagating trust among web pages. However, TrustRank propagates trust among web pages based on the number of outgoing links, which is also how PageRank propagates authority scores among Web pages. This type of propagation may be suited for propagating authority, but it is not optimal for calculating trust scores for demoting spam sites. In this paper,
Undue influence eliminating the impact of link plagiarism on web search rankings.
Link farm spam and replicated pages can greatly deteriorate link-based ranking algorithms like HITS. In order to identify and neutralize link farm spam and replicated pages, we look for sufficient material copied from one page to another. In particular, we focus on the use of “complete hyperlinks” to distinguish link targets by the anchor text used. We build and analyze the bipartite graph of documents and their complete hyperlinks to find pages that share anchor text and link targets. Link farms and replicated pages are identified in this process, permitting the influence of problematic links to be reduced in a weighted adjacency matrix. Experiments and user evaluation show significant improvement in the quality of results produced using HITS-like methods. 1
Topical link analysis for web search.
This paper 1 is concerned with the problem of multimodal fusion in video search. First, we employ an object-sensitive approach to query analysis to improve the baseline result of text-based video search. Then, we propose a PageRank-like graph-based approach to text-based search result re-ranking. To better exploit the underlying relationship between video shots, the proposed reranking scheme simultaneously leverages textual relevancy, semantic concept relevancy, and low-level-feature-based visual similarity. In this PageRank-like scheme, we construct a set of graphs with the video shots as vertexes, and the conceptual and visual similarity between video shots as “hyperlinks. ” A modified topic-sensitive PageRank algorithm is then applied on these graphs to propagate the relevance scores through all related video shots. Experimental results verify the effectiveness of the graphbased propagation approach combined with the object-sensitive query analysis approach, which brings significant improvement to the baseline of text-based video search. Our experimental analysis also indicates that the proposed re-ranking method is highly generic and independent of different query classes, training data, and human interference.
Store%2Dand%2DForward Performance in a DTN.

OS%2Dmulticast On%2Ddemand Situation%2Daware Multicasting in Disruption Tolerant Networks.
Abstract—Disruption Tolerant Networks (DTNs) are emerging solutions to networks that experience frequent network partitions and large end-to-end delays. In this paper, we study how to provide high-performance multicasting service in DTNs. We develop a multicasting mechanism based on on-demand path discovery and overall situation awareness of link availability (OSmulticast) to address the challenges of opportunistic link connectivities in DTNs. Simulation results show that OSmulticast can achieve a better message delivery ratio than existing approaches, e.g. DTBR (a dynamic tree-based routing), with similar delay performance. OS-multicast also achieves better efficiency performance when the probability of link unavailability is high and the duration of link downtime is large. Keywords-Disruption tolerant networks; multicasting I.
Topical TrustRank using topicality to combat web spam.

Detecting semantic cloaking on the web.
By supplying different versions of a web page to search engines and to browsers, a content provider attempts to cloak the real content from the view of the search engine. Semantic cloaking refers to differences in meaning between pages which have the effect of deceiving search engine ranking algorithms. In this paper, we propose an automated two-step method to detect semantic cloaking pages based on different copies of the same page downloaded by a web crawler and a web browser. The first step is a filtering step, which generates a candidate list of semantic cloaking pages. In the second step, a classifier is used to detect semantic cloaking pages from the candidates generated by the filtering step. Experiments on manually labeled data sets show that we can generate a classifier with a precision of 93% and a recall of 85%. We apply our approach to links from the dmoz Open Directory Project and estimate that more than 50,000 of these pages employ semantic cloaking.
Adversarial information retrieval on the web %28AIRWeb 2006%29.

Cloaking and Redirection A Preliminary Study.
Cloaking and redirection are two possible search engine spamming techniques. In order to understand cloaking and redirection on the Web, we downloaded two sets of Web pages while mimicking a popular Web crawler and as a common Web browser. We estimate that 3% of the first data set and 9% of the second data set utilize cloaking of some kind. By checking manually a sample of the cloaking pages from the second data set, nearly one third of them appear to aim to manipulate search engine ranking.
Hybrid semantic tagging for information extraction.

Identifying link farm spam pages.
With the increasing importance of search in guiding today’s web traffic, more and more effort has been spent to create search engine spam. Since link analysis is one of the most important factors in current commercial search engines’ ranking systems, new kinds of spam aiming at links have appeared. Building link farms is one technique that can deteriorate link-based ranking algorithms. In this paper, we present algorithms for detecting these link farms automatically by first generating a seed set based on the common link set between incoming and outgoing links of Web pages and then expanding it. Links between identified pages are reweighted, providing a modified web graph to use in ranking page importance. Experimental results show that we can identify most link farm spam pages and the final ranking results are improved for almost all tested queries.
Identification of Critical Values in Latent Semantic Indexing.
This paper reports the results of a study to determine the most critical elements of the T k and S k D k matrices, which are input to LSI. We are interested in the impact, both in terms of retrieval quality and query run time performance, of the removal (zeroing) of a large portion of the entries in these matrices
Lessons from a Gnutella%2Dweb gateway.
We present a gateway between the WWW and the Gnutella peer-topeer network that permits searchers on one side to be able to search and retrieve files on the other side of the gateway. This work improves the accessibility of files across different delivery platforms, making it possible to use a single search modality. We outline our design and implementation, present access statistics from a test deployment and discuss lessons learned.
Implementing an Evaluation Architecture for Web Proxies.

Lessons from a Gnutella%2Dweb gateway.
We present a gateway between the WWW and the Gnutella peer-topeer network that permits searchers on one side to be able to search and retrieve files on the other side of the gateway. This work improves the accessibility of files across different delivery platforms, making it possible to use a single search modality. We outline our design and implementation, present access statistics from a test deployment and discuss lessons learned.
Toward a unification of text and link analysis.
This paper presents a simple yet profound idea. By thinking about the relationships between and within terms and documents, we can generate a richer representation that encompasses aspects of Web link analysis as well as text analysis techniques from information retrieval. This paper shows one path to this unified representation, and demonstrates the use of eigenvector calculations from Web link analysis by stepping through a simple example.
Learning Web Request Patterns.
Summary. Most requests on the Web are made on behalf of human users, and like other human-computer interactions, the actions of the user can be characterized by identifiable regularities. Much of these patterns of activity, both within a user, and between users, can be identified and exploited by intelligent mechanisms for learning Web request patterns. Our focus is on Markov-based probabilistic techniques, both for their predictive power and their popularity in Web modeling and other domains. Although history-based mechanisms can provide strong performance in predicting future requests, performance can be improved by including predictions from additional sources. In this chapter we review the common approaches to learning and predicting Web request patterns. We provide a consistent description of various algorithms (often independently proposed), and compare performance of those techniques on the same data sets. We also discuss concerns for accurate and realistic evaluation of these techniques. 1
Toward a unification of text and link analysis.
This paper presents a simple yet profound idea. By thinking about the relationships between and within terms and documents, we can generate a richer representation that encompasses aspects of Web link analysis as well as text analysis techniques from information retrieval. This paper shows one path to this unified representation, and demonstrates the use of eigenvector calculations from Web link analysis by stepping through a simple example.

A Non%2DFunctional Prototype at TREC 2003.


Review of Web caching and replication by Michael Rabinovich and Oliver Spatscheck. Addison Wesley 2002.

Predicting web actions from HTML content.
This paper examines the accuracy of predicting a user&#039;s next action based on analysis of the content of the pages requested recently by the user. Predictions are made using the similarity of a model of the user&#039;s interest to the text in and around the hypertext anchors of recently requested Web pages. This approach can make predictions of actions that have never been taken by the user and potentially make predictions that reflect current user interests. We evaluate this technique using data from a full-content log of Web activity and find that textual similarity-based predictions outperform simpler approaches.
HTTP Simulator Validation Using Real Measurements A Case Study.
Simulation is a common technique used by Web researchers and provides many benefits. Verification and validation of a simulator are essential if the results of those simulations are to be believed. Unfortunately, even limited validation of simulators has been uncommon in the Web caching community. In contrast, this paper argues for the validity of a new network and caching simulator by extensively comparing simulated results to both small-- and large-scale realworld HTTP traffic. In addition, we describe some of the preparation needed to use a large, well-known trace of Web usage.
A Web Caching Primer.
This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by sending an email message to pubs-permissions@ieee.org.
Topical locality in the Web.
Most web pages are linked to others with related content. This idea, combined with another that says that text in, and possibly around, HTML anchors describe the pages to which they point, is the foundation for a usable WorldWide Web. In this paper, we examine to what extent these ideas hold by empirically testing whether topical locality mirrors spatial locality of pages on the Web. In particular, we find that the likelihood of linked pages having similar textual content to be high; the similarity of sibling pages increases when the links from the parent are close together; titles, descriptions, and anchor text represent at least part of the target page; and that anchor text may be a useful discriminator among unseen child pages. These results show the foundations necessary for the success of many web systems, including search engines, focused crawlers, linkage analyzers, and intelligent web agents.
Enabling technologies learning to personalize.

Pushing politely improving Web responsiveness one packet at a time.
The rapid growth of traffic on the World-Wide Web results in heavier loads on networks and servers and in increased latency experiencedwhile retrieving web documents. This paper presents a framework that exploits idle periods to satisfy future HTTP requests speculatively and opportunistically. Our proposal differs from previous schemes in that speculative dissemination always gives precedenceto on-demand traffic, uses ranged requests for improved performance, and can be implemented over a connectionless transport. The protocol uses bounded and little server state even as the workload was increased and it is resistant to erroneous estimates of available bandwidth. Substantial latency improvements are reported over pure on-demand strategies. 1
An Early DiscoWeb Prototype at TREC8.

Classification Using an Online Genetic Algorithm.

Highest Utility First Search Across Multiple Levels of Stochastic Design.
Many design problems are solved using multiple levels of abstraction, where a design at one level has combinatorially many children at the next level. A stochastic optimization methods, such as simulated annealing, genetic algorithms and multi-start hill climbing, is often used in such cases to generate the children of a design. This gives rise to a search tree for the overall problem characterized by a large branching factor, objects at di erent levels that are hard to compare, and a child-generator that is too expensive to run more than a few times at each level. We present the Highest Utility First Search (HUFS) control algorithm for searching such trees. HUFS is based on an estimate we derive for the expected utility of starting the design process from any given design alternative, where utility re ects both the intrinsic value of the nal result and the cost in computing resources it will take to get that result. We also present an empirical study applying HUFS to the problem of VLSI module placement, in which HUFS demonstrates signi cantly better performance than the common \waterfall &amp;quot; control method.
Human Performance on Clustering Web Pages A Preliminary Study.
With the increase in information on the World Wide Web it has become difficult to quickly find desired information without using multiple queries or using a topic-specific search engine. One way to help in the search is by grouping HTML pages together that appear in some way to be related. In order to better understand this task, we performed an initial study of human clustering of web pages, in the hope that it would provide some insight into the difficulty of automating this task. Our results show that subjects did not cluster identically; in fact, on average, any two subjects had little similarity in their web-page clusters. We also found that subjects generally created rather small clusters, and those with access only to URLs created fewer clusters than those with access to the full text of each web page. Generally the overlap of documents between clusters for any given subject increased when given the full text, as did the percentage of documents clustered. When analyzing individual subjects, we found that each had different behavior across queries, both in terms of overlap, size of clusters, and number of clusters. These results provide a sobering note on any quest for a single clearly correct clustering method for web pages.
Experiments in UNIX Command Prediction.
A good user interface is central to the success of most products. Our research is concerned with improving an interface by making it adaptive --- changing over time as it learns more about the user. In this paper we consider the task of modifying a UNIX shell to learn to predict the next command executed as one sample adaptive user interface. To this end, we have collected command histories (some extensive) from 77 people, and have calculated the predictive accuracy for each of five methods over this dataset. The algorithm with the highest performance produces an average online predictive accuracy of up to 38%. 1 Introduction  A good user interface is central to the success of operating systems, applications, and in general, most consumer products. Our research is concerned with improving an interface by making it adaptive --- changing over time as it learns more about the user. To this end, we have collected and analyzed a sizable set of command usage histories from which we may deter...
An Adaptive UNIX Command%2DLine Assistant.
This paper describes our ongoing efforts on building such patternrecognizing agents into a UNIX shell, in particular, through the addition of a personalized software agent --- a &#034;personal assistant&#034; (Mitchell et al. 1994) --- to the UNIX shell tcsh.
Toward an Adaptive Command Line Interface.
This paper explores different mechanisms for predicting the next command to be used for the UNIX command-line shell. We have collected command histories from 77 people, and have calculated the predictive accuracy for each of five methods over this dataset. The algorithm with the best performance has an average online predictive accuracy of up to 45%.
